package class29;

import com.sun.xml.internal.bind.v2.model.core.ID;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class MaxSubSequence {

    public static int lcs(String s1,String s2){
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int N  = str1.length;
        int M = str2.length;
        return process(str1,str2,N-1,M-1);
    }

    public static int process(char[] str1,char[] str2,int i1,int i2){
        if (i1 == 0&& i2==0){
            return str1[i1]==str2[i2]?1:0;
        }
        if (i1==0){
            return ((str1[i1]==str2[i2])||process(str1,str2,i1,i2-1)==1)?1:0;
        }
        if (i2==0){
            return ((str1[i1]==str2[i2])||process(str1,str2,i1-1,i2)==1)?1:0;
        }

        int p1 = process(str1,str2,i1-1,i2-1);
        int p2 = process(str1,str2,i1,i2-1);
        int p3 = process(str1,str2,i1-1,i2);
        int p4 = 0;
        if (str1[i1]==str2[i2]){
            p4=p1+1;
        }
        return Math.max(Math.max(p1,p2),Math.max(p3,p4));
    }

    public static int dp(String s1,String s2){
        char[] str1 =s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int N = str1.length;
        int M = str2.length;
        int[][] dp = new int[N][M];
        dp[0][0] = str1[0]==str2[0]?1:0;
        for (int i = 1;i<N;i++){
            dp[i][0] = str1[i] == str2[0]?1:dp[i-1][0];
        }
        for (int i = 1;i<M;i++){
            dp[0][i] = str1[0] == str2[i]?1:dp[0][i-1];
        }
        for (int i = 1;i<str1.length;i++){
            for (int j =1;j<str2.length;j++){
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                if (str1[i] == str2[j]){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1);
                }
            }
        }
        return dp[N-1][M-1];
    }

    public static void main(String[] args) {
        String str1 = "ab1c2";
        String str2 = "12op";
        System.out.println(lcs(str1,str2));
        System.out.println(dp(str1,str2));
    }

    public static String maxSubSequence(String str1,String str2){
        if (str1 ==null||str1.equals("")|| str2==null||str2.equals("")){
            return "";
        }
        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();
        int len1 = c1.length;
        int len2 = c2.length;
        int[][] dp = new int[len1][len2];

        //第一行
        for (int i = 0;i<len2;i++){
            dp[0][i]=c2[i]==c1[0]?1:dp[0][i-1];
        }
        //第一列
        for (int i = 0;i<len1;i++){
            dp[i][0] = c1[i]==c2[0]?1:dp[i-1][0];
        }

        for (int i = 1;i<len1;i++){
            for (int j =1;j<len2;j++){
                int p1 = 0;
                int p2 = 0;
                int p3 = 0;
                int p4 = 0;
                if (c1[i] == c2[i]){
                    p1 = dp[i-1][j-1]+1;
                }else if (c1[i-1] == c2[j]){
                    p2 =dp[i-1][j];
                }else if (c1[i] == c2[j-1]){
                    p3 = dp[i][j-1];
                }else {
                    p4 = dp[i-1][j-1];
                }
                dp[i][j] = Math.max(p1,Math.max(p2,Math.max(p3,p4)));
            }
        }

        int maxSubSeq = dp[len1-1][len2-1];
        char[] res = new char[maxSubSeq];
        int index = maxSubSeq -1;
        len1 = len1-1;
        len2 = len2-1;
        while (index>=0){
            if (len2>0&&dp[len1][len2]==dp[len1][len2-1]){
                len2--;
            }else if (len1 >0 && dp[len1][len2] ==dp[len1-1][len2]){
                len1--;
            }else {
                res[index--] = c1[len1];
                len1--;
                len2--;
            }
        }
        return String.valueOf(res);
    }
//
//    public static void main(String[] args) {
//        String str1 = "amghnbcni";
//        String str2 = "atlgnbfvi";
//        System.out.println(maxSubSequence(str1,str2));
//    }
}
